package backtracking;

import java.util.*;

//todo
public class combinationSumii40 {

    Set<Integer> resultSet = new HashSet<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList();
        backtracking(candidates,0,target,result,new ArrayList<>());
        return result;

    }

    private void backtracking(int[] candidates, int i,int target, List<List<Integer>> result, ArrayList<Integer> cur) {
        if(target == 0 && !contains(cur)){
            result.add(new ArrayList(cur));
            return;
        }
        if(i==candidates.length || target<0){
            return;
        }

        cur.add(candidates[i]);
        backtracking(candidates,i+1,target-candidates[i],result,cur);
        cur.remove(cur.size()-1);
        backtracking(candidates,i+1,target,result,cur);
    }

    private boolean contains(ArrayList<Integer> cur) {
        List<Integer> list = new ArrayList<>(cur);
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        StringBuilder key = new StringBuilder();
        for (Integer integer:list
        ) {
            key.append(integer);
        }
        if(resultSet.contains(Integer.parseInt(key.toString()))){
            return true;
        }else {
            resultSet.add(Integer.parseInt(key.toString()));
            return false;
        }
    }

}
